/*
 * @lc app=leetcode.cn id=630 lang=cpp
 *
 * [630] 课程表 III
 */

// @lc code=start
class Solution
{
public:
    static bool cmp(const vector<int> &a, const vector<int> &b)
    {
        return a[1] < b[1];
    }

    int scheduleCourse(vector<vector<int>> &courses)
    {
        //将课程结束时间按升序排序
        sort(courses.begin(), courses.end(), cmp);
        //大根堆，将课程持续时间最长的课放在堆顶
        priority_queue<int, vector<int>, less<>> q;
        int sum = 0;
        //从课程结束时间最早的开始加入堆中，如果碰到总课程时间大于课程结束时间
        //就把当前队列中最耗时的课程给弹出队列，借此贪心保证学习的课程最多
        //怎么证明？
        for (const vector<int> &course : courses)
        {
            int d = course[0], e = course[1];
            sum += d;
            q.push(d);
            if (sum > e)
            {
                sum -= q.top();
                q.pop();
            }
        }
        return (int)q.size();
    }
};
// @lc code=end
